package com.jeff.practice;

import java.util.LinkedList;
import java.util.Queue;

public class Test11 {


    public static void main(String[] args) {
        Test11 solution = new Test11();
        char[][] grid = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '0', '1', '1'},
                {'0', '0', '0', '0', '0'},
                {'0', '1', '1', '0', '0'},};
        System.out.println(solution.numIslands(grid)); // 输出: 3
    }


    public int numIslands(char[][] grid) {
        // 首先判断边界条件
        if (grid==null||grid.length==0){
            return 0;
        }
        // 定义遍历的行数和列数
        int rows=grid.length;
        int cols=grid[0].length;
        //定义标记数组，用于记录是否访问过
        boolean[][] visited=new boolean[rows][cols];
        int islandCount=0;
        //遍历元素
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                //判断当前位置是否为岛屿，并且未被访问过 满足这个条件才可以让大陆数量加一
                if (grid[r][c]=='1'&&!visited[r][c]){
                    bfs(grid,visited,r,c);
                    islandCount++;
                }
            }
        }

        return islandCount;
    }

    //广度优先遍历
    private void bfs(char[][] grid, boolean[][] visited, int r, int c) {
        //定义队列
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{r,c});
        visited[r][c]=true;
        //定义四个方向（上下左右）
        int[][] directions={{-1,0},{1,0},{0,-1},{0,1}};
        //当队列不为空就继续遍历
        while (!queue.isEmpty()){
            //从队列中取出一个位置
            int[] position=queue.poll();
            //构建新的坐标
            for (int[] direction : directions) {
                int newRow=position[0]+direction[0];
                int newCol=position[1]+direction[1];
                //判断边界条件与标记数组判断是否可以访问 如果可以访问就入队
                if (newRow>=0&&newRow<grid.length&&newCol>=0&&newCol<grid[0].length&&grid[newRow][newCol]=='1'&&!visited[newRow][newCol]){
                    queue.offer(new int[]{newRow,newCol});
                    visited[newRow][newCol]=true;
                }
            }


        }
    }
}
